During the startup loading (commonly denoted as a “bootstrap” loading, a “boot”, or “booting”) into a computer's main memory of an operating system from a mass storage device, for certain mass storage device classes it is assumed that the device is characterized by a set of parameters traditionally-associated with the geometry of early disk drive devices. These parameters are referred to as “CHS” parameters (for the “Cylinder-Head-Sector” arrangement of the early disk drives). A head defines a plane (physically, the disk surface which the head reads and writes). A track is geometrically the (circular) intersection of a cylinder and the plane specified by a head. There are the following parameters in CHS notation:                three constant integers describe the geometry and specify the total number of sectors of a mass storage device:                    C, the total number of cylinders;            H, the total number of heads; and            S, the number of sector per track.                        three variable integers define the address of a sector in a mass storage device.                    c, the cylinder number (between 0 and C-1);                        h, the head number (between 0 and H-1); and        s, the sector number within the track (between 1 and s).“Active” and “Bootable” Partitions        
The storage area of a mass storage device is typically “partitioned”, or divided into logically separate areas. Even if the entire usable storage area is devoted to a single such partition, the device is said to be partitioned. For a mass storage device to be capable of boot-loading an operating system, exactly one partition must be designated as the “active” partition. An active partition is designated with a Boot Indicator flag equal to 80h in the Partition Table (detailed below). A partition containing executable code capable of directly or indirectly loading an operating system is denoted as a “bootable” partition. More than one partition may contain executable code for loading an operating system (and thus be bootable), but only the currently-designated active partition is selected for booting at startup. The active partition is thus intended to be bootable, but in practice the active partition may fail to boot the system. There are various conditions which result in a boot failure, one of which involves incompatibilities between the computer's Basic I/O System (BIOS) and the geometrical configuration specified for the mass storage device, as covered in detail below.
Prior-Art Startup Loading Sequence
FIG. 1 is a flowchart of a prior art procedure for startup loading of an operating system. In a starting point 10, the computer is started, and in a step 15, the BIOS initiates a “Power-On Self Test” (POST) of the hardware. In a step 20, the BIOS searches for a storage device capable of startup loading. (For compactness and clarity, the drawings refer to startup loading as “boot”.) At a decision point 22, if such a device is not found, the process aborts in a termination 50. If such a device is found, in a step 25 the BIOS loads the first physical sector, known as the “Master Boot Record” (MBR). In a step 30, a search is conducted for an active partition on the device. At a decision point 32, if an active partition is not found, the process aborts in termination 50. If an active partition is found, in a step 35 the executable code obtained from the MBR is run to load into the computer's memory the bootable partition sector containing the executable code for startup loading (herein denoted as the “boot sector”) using the BIOS “Read Sector” function Int13h function 02. In a step 40 the executable code obtained from the boot sector is run to find and execute the operating system loader, which then loads the operating system in a step 45. Finally, control is transferred to the loaded operating system, to terminate the startup loading process, in a termination 48.
It is noted that in mass storage devices having a capacity of 8.4 GB or less, the MBR uses “Enhanced CHS” parameters (at byte offset 01, 02, and 03, in the Partition Table, as is detailed below).
The first sector in the active partition contains bootstrap code and a “BIOS Parameter Block” (BPB) table (see Table 2). The BPB contains information used by the operating system to access the mass storage device. On computers running NT-based Windows, the executable code in the boot sector finds the operating system loader (the system file “ntldr”), which is then loaded into memory, after which the boot sector code transfers execution to the loader. The operating system loader uses parameters from the MBR and the BPB to continue the boot. For example, in a multi-operating system boot, the loader reads the MBR to find the start of the second partition. Other actions may be taken, depending the specific operating system and the specific loader involved.
As noted above, for certain storage device classes, access to the sectors of the storage device is achieved by specifying CHS parameters. In this case, FIG. 1 illustrates an optimistic scenario, where the CHS parameters available to the BIOS correspond to those of the storage device, and thus access to the boot sector is successful. As detailed below, however, it can happen that the CHS parameters available to the BIOS do not correspond to those of the storage device, in which case access to the device will fail.
Incompatibility Fundamentals
The incompatibility problem arises fundamentally because there are inherent limitations in the CHS parameter scheme. The ability of CHS parameters to address sectors of mass storage suffers from certain shortcomings that limits the usable amount of storage. For example, the conventional BIOS interface supports a maximum of 1024 cylinders, a maximum of 256 heads, and a maximum of 63 sectors per track. These result in a limit of 8.4 GB in a mass storage device for a conventional BIOS. A larger, more modern mass storage device, however, might be configured with 65536 cylinders, 16 heads, and 255 sectors per track, for a storage of 136.9 GB. Unfortunately, with the conventional BIOS such a device can be used only with 1024 cylinders (the BIOS limit), 16 heads (the device limit), and 63 sectors per track (the BIOS limit), for a total storage of only 504 MB—less than 0.4% of the actual storage device capacity. The limit shown in this example is encountered with IDE mass-storage disk drives (on account of the 16-head limit for IDE drives), and is frequently referred to as the “504 MB barrier”.
Overcoming CHS Limitations
In response to an increasing need for larger mass storage devices, developers have employed various techniques to bypass such limitations. One technique is to use “Logical Block Addressing” (LBA), which does not depend on storage device geometry. Unfortunately, however, not all storage devices support LBA. For those which do not support LBA, CHS references are necessary. Some typical techniques for adapting CHS references include, but are not limited to: employing a false geometry for “geometrical translation” of the storage device, which accommodates the conventional BIOS limit, and which eases the restriction thereof; and “bit shifting”, by which the BIOS can consider the storage device as having an increased number of heads to compensate for the reduced number of cylinders. “Geometrical translation” is detailed as follows:
The term “geometrical translation scheme” herein denotes the manner and algorithmic rules by which a BIOS performs geometrical translation. FIG. 4A conceptually illustrates the process of geometrical translation. A device geometrical configuration 291 features parameters C, H, and S, as described above. The physical disk drive and/or the controller thereof make reference to these C, H, and S parameters. Device geometrical configuration 291 may be used even by a disk drive which does not actually have the specific physical structure implied by the C, H, and S parameters. In fact, the use of device geometrical configuration 291 is not limited to physical disk drives, but may be observed by a data storage device whose actual physical structure is completely unrelated to a disk drive. In a geometrical translation operation 293, device geometrical configuration 291 is mapped into a translated geometrical configuration 295 with parameters C′, H′, and S′. The BIOS, and thus the operating system access data storage according to these C′, H′, and S′ parameters. Thus, the terms “translated geometrical configuration” and “translated geometry” refer to translated geometrical configuration 295 as utilized by the BIOS (and thus the operating system) for data storage access. In contrast, the terms “device geometrical configuration” or “geometrical configuration” without any qualifiers herein refer to device geometrical configuration 291 as seen and used by the mass storage device and/or the controller thereof.
Unfortunately, not all BIOS geometrical translation schemes are compatible from one BIOS to another. That is, for a given mass storage device, the geometrical translation scheme of one BIOS may produce a different translated geometrical configuration from that of another BIOS. As a result, problems may arise when a storage device configured on one computer is transferred to a computer having a different BIOS. The CHS parameters stored in the Partition Table are assumed by prior art startup loading code to correspond to the CHS parameters returned by the BIOS “Get Device Parameter” function (“Int13h function 08”). If this is not the case—if the geometrical configuration in the Partition Table does not match the translated geometrical configuration of the BIOS geometrical translation scheme—the startup loading process will fail because the BIOS “Read Sector” function (“Int13h function 02”) will be relying on incompatible geometrical parameters.
It is noted that the BIOS Int13h function 08 “Get Device Parameter” function is used to obtain CHS parameter values from the BIOS. These are also denoted herein as “runtime” CHS parameter values. In contrast, CHS parameter values which were previously written to the BIOS Parameter Block, and are subsequently obtained by reading therefrom, are denoted herein as “recorded” CHS parameter values.
BIOS and BIOS Parameter Block Incompatibilities
As noted previously, if there is a fatal incompatibility between the BIOS used to set up and configure the mass storage device and the BIOS of the computer for which the mass storage device is to boot, the boot will fail.
There is also a related problem if there exists an incompatibility between the BIOS of the computer on which the mass storage device operates and the BPB recorded on the mass storage device. This incompatibility prevents the operating system from being able to properly access the device.
Logical Block Addressing
In the alternative “Logical Block Addressing” scheme, the sectors are numbered sequentially, starting at 0. The use of LBA notation is simpler than CHS and, as noted, does not depend on the internal geometry of a mass storage device. Unfortunately, however, for certain mass storage devices, it is the CHS parameters which are recorded in the BIOS Parameter Block (BPB) of the mass storage device, and which must be used for accessing that mass-storage device. (The BPB is stored in the boot sector, which is the first sector of an active partition of the mass storage device.) In addition, the location and extent of the active partition on the mass storage device is also recorded in the Partition Table of the MBR in terms of CHS parameters. As a result, there is currently no general solution for the problem of incompatibility that can occur when interchanging a mass storage device from one computer to another. Due to vast range of computer hardware (motherboards) and hard disk capacities, a mass storage device formatted and configured on one computer might not function properly on another computer. Data stored by the first computer on the storage device might be inaccessible to the second computer.
The Need for Interchangeability
The current trend is to make computer components easy to integrate. Typically, modem component devices have “plug-and-play” capability, giving users the ability to simply plug the device into a computer and let the computer handle the adaptations necessary to utilize that device. As detailed above, however, primary mass storage devices do not interchange from one computer to another so easily. The incompatibilities from one mass storage device to another are at a fundamental level involving the basic hardware of the computer, and are generally unreachable by “plug-and-play” techniques, which function at a higher level, via the operating system. Such devices must function at the basic hardware level not only to achieve high efficiency and rapid response, but because they have to be operative before the operating system has been loaded. Thus, without a solution to the incompatibility problem in interchanging mass-storage devices within a computer, the typical computer is sold to the user with the primary mass storage device already formatted and configured for use with that computer.
Need for Inter-System Compatibility of Mass Storage Devices
It is highly desirable to be able to manufacture and sell off-the-shelf mass storage devices with embedded applications that can boot and run on any type of hardware and BIOS. For example, it would be desirable to be able to develop a particular complex application in complete form and functional environment (perhaps even with a specialized operating system) by setting up the application on a relatively-inexpensive mass storage device and then marketing and distributing the mass storage device as a stand-alone merchandisable commodity. A user wishing to employ that application need only purchase the mass storage device, which would be plugged into an existing computer, which would boot and run the application immediately. Unfortunately, the current limitations described above do not allow such products to be freely marketed, and thus the growing embedded systems market is currently deprived of significant potential.
Summary of Prior Art and the Limitations Thereof
The concept of configuring a system to handle a variety of storage medium formats is known in other areas. For example, U.S. Pat. No. 4,928,192 to Bartlett, et al. (herein denoted as “Bartlett”) discloses methods for adapting a computer to automatically handle different floppy disk formats regarding the presence or absence of servo information recorded in the media tracks. That is, Bartlett addresses variations in the physical recording process for the media. Bartlett, however, is specific to processes used with early floppy disk drives, and is not applicable to storage devices in general, particularly those of high capacity. Moreover, Bartlett does not address the issue of bootstrap loading. U.S. Pat. No. 5,430,855 to Walsh, et al. (herein denoted as “Walsh”) discloses methods of using physically dissimilar disk drives (e.g., with different capacities and data rates) together in the same array despite their dissimilarities. Walsh, however, does not address the problem of mass storage device interchange regarding operation prior the loading of the operating system.
U.S. Pat. No. 5,721,952 to Lin, et al. (herein denoted as “Lin”) addresses the device interchange problem as discussed in the present application, and discloses a method for automatically detecting the geometrical configuration of a disk drive. Lin also discloses that the software for this can be incorporated into the computer's BIOS for automatic detection prior to bootstrap loading. However, Lin does not address the problem of incompatibility in geometrical translation of storage device parameters, nor does Lin provide a means of adapting a storage device to be bootable on all computers. That is, Lin provide software for the BIOS of a computer, so although a computer according to Lin may be able to adapt to different storage devices, Lin does not solve the problem of allowing the storage device to adapt to different computers. This latter limitation is the problem addressed by the present invention.
U.S. Pat. No. 6,138,222 to Wyde, et al. (herein denoted as “Wyde”) discloses a method of geometrical translation for adapting large-capacity disk drives to the limited addressing schemes in older computers. Wyde does not discuss overcoming the incompatibility of different geometrical translation schemes in general. Moreover, like Lin, Wyde also does not address the issue of adapting a storage device to be bootable on all computers.
Thus, many problems are seen to arise on account of using the obsolete CHS parameters for storage access. Despite the recognition of many of these problems, however, there is currently no solution to the bootable storage device interchange problem and the market need for inter-system compatibility of mass storage devices.
As described previously, the dependency between the preparation of the mass storage device and the actual startup loading process, requires the partition and format of the mass storage device to be done using the hardware and BIOS of the target computer (the computer in which the device is to be installed) to assure successful startup loading. If the preparation is done using different hardware or a different BIOS, it is possible that there will be an incompatibility with the enhanced CHS geometrical translation, causing a failure to load the operating system on startup.
Therefore, it is desirable to be able to supply mass storage devices ready for installation and use, without the need for formatting and configuration on the target computer. There is thus a widely recognized need for, and it would be highly advantageous to have, a method for configuring a storage device on one computer such that the storage device will load the operating system when installed on another computer regardless of the BIOS employed on that other computer. This goal is achieved by the present invention.
Details of Prior Art Limitations
To appreciate the novelty of the present invention, it is worthwhile to first present the following review of the prior art and the limitations thereof:
Preparing a Device for Startup Loading
In order to use a mass storage device for startup loading of an operating system, the device must undergo a preparation process. (A storage device capable of startup loading an operating system is herein denoted as a “bootable” device.) Utilities such as the DOS FDISK or the Windows NT Setup program prepare and partition the device, as described below and in FIG. 3. “Formatting” is the operation by which logic divisions called partitions are created in a mass storage device, and a file system capability is set up. A file system manages the way in which files are created and named, and where the files are placed logically for storage and retrieval. Certain types of mass storage devices, such as hard disk drives, are typically furnished by the manufacture in an unformatted condition and are formatted when installed on the computer.
FIG. 3 is a flowchart of a prior-art procedure for preparing a mass storage device for use as a bootable device in a computer. In a step 210, the mass storage device is cleared of all data, if necessary. A new device direct from the manufacturer will normally not need step 210. Next, in a step 220 at least one partition (a logical division) is created on the mass storage device, and a Master Boot Record (MBR) with a partition table is set up on the device. The MBR contains a defined amount of space for executable code and a partition table typically having four entries. Each entry defines one partition location on the storage device (see FIG. 4B and the description below). In a step 230, the first byte in exactly one of the entries is set to mark the corresponding partition as “active” or “bootable”. Then, in a step 240, the partitions are formatted. The formatting process creates a boot sector at the beginning of each partition (the boot sector is the first sector of a partition). The boot sector is critical for starting the computer. The boot sector contains executable code and data required by the executable code, including crucial information that file system loader uses to access the device. The executable code is operating system-dependent, and in some situations, new executable code must be written in the boot sector in a conditional step 250. For example, configuring a storage device to load Windows XP embedded typically starts by using FDISK to create a partition by, and then requires rewriting the boot sector (in step 250) with a “BootPrep” utility to replace the DOS-oriented executable code in the boot sector with Windows NT-oriented code. Following this formatting process, in a final step 260 the operating system image is copied to the partition.
Storage Device Organization and Storage Allocation
FIG. 4B is a diagram of the prior-art allocation of storage in a Master Boot Record. An area 271 is reserved for executable code. An area 273 is for the first partition entry; an area 275 is for the second partition entry; an area 277 is for the third partition entry; and an area 279 is for the fourth partition entry. An area 281 is for a “signature” that enables verifying the partition table area. The signature is a constant 2-byte value equal to 55AAh. Addresses 283 show the beginning and end address of each area Each of the entries 273, 275, 277, and 279 is allocated 16 bytes.
One purpose of the partition table is to specify the physical start and end sectors of the partitions. The two addressing notation schemes discussed above, CHS and LBA, are represented in the partition entries as shown in the table below:
TABLE 1Partition Table dataByte OffsetField LengthDescription00BYTEBoot Indicator01BYTEBeginning Head02 6 bitsBeginning Sector0310 bitsBeginning Cylinder04BYTESystem ID05BYTEEnding Head06 6 bitsEnding Sector0710 bitsEnding Cylinder084 BYTESBeginning sector (LBA notation)124 BYTESNumber of sectors in partition(LBA notation)
The partition table contains 16 bytes of data, from byte 00 through byte 15. The beginning of the partition is indicated in CHS notation in bytes 01 through 03. The end of the partition is indicated in CHS notation is bytes 05 through 07. The beginning of the partition is indicated in LBA notation in bytes 08 through 11, and the number of sectors in the partition is indicated in bytes 12 through 15. Although LBA notation is much simpler and more supportive of larger mass storage devices than CHS notation, as noted previously, not all storage devices support LBA.
BIOS Parameter Block (BPB)
Partial contents of a BPB are illustrated in Table 2 below.
TABLE 2Partial BIOS parameter Block (BPB)ByteOffsetField LengthSample ValueField Name0x0BWORD0x0002Bytes Per Sector0x0DBYTE0x08Sectors Per Cluster0x0EWORD0x0000Reserved Sectors0x103 BYTES0x000000always 00x13WORD0x0000not used by NTFS0x15BYTE0xF8Media Descriptor0x16WORD0x0000always 00x18WORD0x3F00Sectors per Track0x1AWORD0xFF00Number of Heads0x1CDWORD0x3F000000Hidden Sectors0x20DWORD0x00000000not used by NTFS0x24DWORD0x80008000not used by NTFS0x28LONGLONG0x4AF57F0000000000Total Sectors0x30LONGLONG0x0400000000000000Logical ClusterNumber0x38LONGLONG0x54FF070000000000Logical ClusterNumber0x40DWORD0xF6000000Clusters Per FileRecord0x44DWORD0x01000000Clusters Per IndexBlock0x48LONGLONG0x14A51B74C91B741CVolume SerialNumber0x50DWORD0x00000000ChecksumThe Origins of Incompatible Sector Addressing Schemes
In reality, no currently-manufactured mass storage devices actually have the physical geometry implied by CHS notation, but this obsolete system of sector addressing is still used when employing BIOS services. As mentioned previously, the primary interface to BIOS services is the Int13h software interrupt. The Int13h interface supports many different functions, such as reading, writing, and formatting the storage device. Using Int13h, however, requires knowing the specific geometry parameters associated with the mass storage device (even if these parameters are unrelated to the actual physical geometry of the device), and providing exact cylinder, head and sector addressing to the routines to allow device access. This has led to incompatibility problems. Due to lack of planning and coordination, there have arisen two different specifications for the allocation of bits to represent the geometrical configuration:                The Int13h interface allocates 24 bits for specifying storage device geometry, broken up as follows:                    10 bits for the cylinder number, for up to 1,024 cylinders.            8 bits for the head number, for up to 256 heads.            6 bits for the sector number, for up to 63 sectors.                        The IDE hard disk standards specify a 28-bit allocation, broken up as follows:                    16 bits for the cylinder number, for up to 65,536 cylinders.            4 bits for the head number, for up to 16 heads.            8 bits for the sector number, for up to 256 sectors.                        
As noted in the example given previously, incompatibilities between these two systems might result in an inability to access up to 99.6% of the storage capacity of a large modern mass storage device, due to the 504 MB barrier.
Prior-Art Techniques for Overcoming CHS Limitations
The previously-mentioned technique of geometrical translation is the most common solution to overcome the 504 MB barrier. This is achieved by using an “enhanced” BIOS that supports BIOS geometrical translation. An enhanced BIOS translates CHS disk parameters to “enhanced CHS” parameters. In this scheme, the BIOS gets CHS parameters according to the IDE hard disk specification and translates those parameters to a different CHS geometrical configuration for use with operating systems using the Int13h 24-bit interface specification.
CHS geometrical translation is valid for devices with capacities up to 8.4 GB that use all 24 bits of the Int13h allocation (1024 cylinders*256 heads*63 sectors per track*512 bytes per sector=8.4 GB).
Mass storage devices with capacities over 504 MB and up to 8.4 GB commonly conform to the Int13h sector limit of 63 sectors. This makes a simple CHS geometrical translation “bit-shifting” scheme possible, in which the number of cylinders is divided by 2, 4, 8 or 16, while the number of heads is multiplied by the same number. The number of sectors per track is unchanged. The use of bit-shifting to accomplish the division and multiplication requires relatively little code and operates at high speed.
In a bit-shifting geometrical translation scheme, if C, H, S, c, h, and s are the original parameters and a prime symbol (′) denotes translated parameters (i.e., C′, H′, S′, c′, h′, and s′), then:
C′=C/N
H′=H*N, where N is the smallest power of two that will ensure C′≦1024; and
S′=S
With mass storage devices having more than 63 sectors, the geometrical translation requires a more complex algorithm and code.